package 树;

import 抽象数据类型.TreeNode;
import 树.遍历.LevelTraverse;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @description:
 * @author: ywk 前序和中序构造二叉树
 * @date: 2020-06-21
 */
public class 构造树 extends LevelTraverse {
    public static int preIndex = 0;
    public static void main(String[] args) {
        String[] pre = ("A,B,D,E,C,F").split(",");
        String[] mid = ("D,B,E,A,F,C").split(",");
        levelOrder(BuildTreeVoid(pre, mid, 0, pre.length-1));

    }

    //构造树
    public static TreeNode buildTree(int[] arr) {
        Queue<TreeNode> queue = new ArrayDeque();
        TreeNode root = null;
        int size;
        TreeNode temp;
        if (root == null) {
            root = new TreeNode(arr[0]);
            queue.offer(root);
        }
        for (int i = 0; i < arr.length && !queue.isEmpty(); ) {
            size = queue.size();
            while (size != 0) {
                temp = queue.poll();
                if (i + 1 < arr.length) {
                    i = i + 1;
                    if (arr[i] == 0) {
                        temp.left = null;
                    } else {
                        temp.left = new TreeNode(arr[i]);
                        queue.offer(temp.left);
                    }

                }
                if (i + 1 < arr.length) {
                    i = i + 1;
                    if (arr[i] == 0) {
                        temp.right = null;
                    } else {
                        temp.right = new TreeNode(arr[i]);
                        queue.offer(temp.right);
                    }

                }
                size--;

            }
        }

        return root;
    }


    public static TreeNode BuildTreeVoid(String[] pre, String[] mid,int start,int end) {
        if (start > end) {
            return null;
        }
        TreeNode newNode = new TreeNode(pre[preIndex]);
        preIndex++;
        if (start == end) {
            return newNode;
        }
        int inIndex = Search(mid, start, end, newNode.getVal());

        newNode.setLeft(BuildTreeVoid(pre, mid, start, inIndex - 1));
        newNode.setRight(BuildTreeVoid(pre, mid, inIndex + 1, end));
        return newNode;
    }

    private static int Search(String[] mid, int start, int end, Object val) {
        if (val instanceof String) {
            for (int i = 0; i < mid.length; i++) {
                if (val.toString().equalsIgnoreCase(mid[i])) {
                    return i;
                }
            }
        }
        return -1;
    }
}
